package com.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

/**
 * @author yijy
 * @description
 * @create 2021/3/30 下午8:11
 **/
public class Page {

    public static void main(String[] args) {
        int[] arr = {1,2,100,4};
        System.out.println(new Page().getMax(arr) );
//        System.out.println(new Page().cardGame(arr,4) );
    }

    public int getMax(int[] arr)
    {
        int n = arr.length;
        if (n == 0)
            return 0;
        int[][] f = new int[n][n];
        int[][] s = new int[n][n];
        for (int i = n - 1; i >= 0 ; i--)
        {
            f[i][i] = i;
            for (int j = i + 1; j < n; j++)
            {
                f[i][j] = Math.max(arr[j] + s[i][j - 1],arr[i] + s[i + 1][j]);
                s[i][j] = Math.min(f[i+1][j],f[i][j-1]);
            }
        }
        return Math.max(f[0][n - 1], s[0][n - 1]);
    }

    public int cardGame(int[] arr, int n) {

        if(arr==null||n==0){return 0;}

        return Math.max(f(arr,0,n-1),s(arr,0,n-1)); // write code here

    }




    public int f(int[]arr,int start,int end){

        if(start==end){return arr[start];}

        return Math.max(arr[start]+s(arr,start+1,end),arr[end]+s(arr,start,end-1));

    }

    public int s(int[]arr,int start,int end){

        if(start==end){return arr[start];}

        return Math.min(f(arr,start+1,end),f(arr,start,end-1));
    }


}
